#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>

#define TIME_DIFF(t1, t2) \
  ((t2.tv_sec - t1.tv_sec) * 1000000 + (t2.tv_usec - t1.tv_usec))

#define MAX(a,b) ((a)>(b)?(a):(b))

int numT = 0;

#define DIM 8191//63
#define GRAIN 16

int image[DIM+1][DIM+1];


volatile int celluled[GRAIN][GRAIN];
volatile int cellulem[GRAIN][GRAIN];

volatile int cont = 1;

#include "spirale.c"



void first_touch()
{
  int i,j ;

  for(i = 0; i<=DIM ; i++)
    {
      for(j = 1; j<=DIM ; j+=512)
	image[i][j]= 0 ;
    }
}


void identifier_pixel()
{
  int i,j;
  for(i = 1; i<DIM ; i++)
    for(j = 1; j<DIM ; j++)
      image[i][j]=image[i][j]*(i*DIM+j);
}


void 
afficher()
{
  int i,j;
  for (i=0; i < DIM; i++)
    {
      for(j=0; j < DIM; j++)
	printf("%4d ", image[i][j]);
      putchar('\n');
    }
  
}



int monter_max(int i_d, int j_d, int i_f, int j_f)
{
  int i,j;
  int changement = 0;
  for (i=i_d; i >= i_f; i--)
      for (j=j_d; j >= j_f; j--)
	if (image[i][j])
	  { 
	    int m;
	    m = MAX(image[i+1][j] , image[i][j+1]);
	    if (m > image[i][j])
	      {	    
		changement = 1;
		image[i][j] = m;
	      }
	  }
  return changement;
}


int descendre_max(int i_d, int j_d, int i_f, int j_f)
{
  int i,j;
  int changement = 0;
  for (i=i_d; i <= i_f; i++)
    for (j=j_d; j <= j_f; j++)
      { 
	if (image[i][j])
	  {
	    int m = MAX(image[i-1][j] , image[i][j-1]);
	    if (m > image[i][j])
	      {	    
		changement = 1;
		image[i][j] = m;
	      }
	  }
      }
  return changement;
}


void 
lancer_descente(int i, int j)
{
  // celluled gere les dependances entre blocs pour la descente
  // celluled[x][y] == 0 <==> les blocs [x-1][y] et [x][y-1] ne sont pas termines
  // celluled[x][y] == 1 <==> un des blocs [x-1][y] et [x][y-1] a termine
  // celluled[x][y] == 2 <==> les blocs [x-1][y] et [x][y-1] sont termines

  celluled[i][j]++;
  if (celluled[i][j] != 2 && i != 0 && j != 0)
    return;
  
  celluled[i][j]= 0; 
  if(descendre_max(i*(DIM/GRAIN),(j*(DIM/GRAIN)),(i+1)*(DIM/GRAIN),(j+1)*(DIM/GRAIN))) 
    cont = 1;
  
  if (j < GRAIN -1)
    lancer_descente(i,j+1);
  if (i < GRAIN - 1)
    lancer_descente(i+1,j);
  
}

void
lancer_monte(int i, int j)
{

  cellulem[i][j]++;
  if (cellulem[i][j] != 2 && i != GRAIN-1 && j != GRAIN-1)
    return ;

  cellulem[i][j]= 0;

  if (monter_max((i+1)*(DIM/GRAIN),((j+1)*(DIM/GRAIN)),(i)*(DIM/GRAIN),(j)*(DIM/GRAIN)))
	cont = 1;
  if (j > 0)
    lancer_monte(i,j-1);
  if (i > 0)
    lancer_monte(i-1,j);
}




int 
main()
{

  struct timeval tv1,tv2;

  regulier(1,DIM,1,DIM,2,4);
  identifier_pixel();
 
  gettimeofday(&tv1,NULL);

  do {
      cont = 0; 
      lancer_monte(GRAIN-1,GRAIN-1);
      lancer_descente(0,0);
      //afficher();
  }  while(cont);

  gettimeofday(&tv2,NULL);
  printf("%d %f\n", numT, ((float)TIME_DIFF(tv1,tv2)) / 1000);  

  return 0;
}
